package Year_2024.Feb;

import Utils.StringUtils;

//https://leetcode.com/problems/minimum-window-substring/?envType=daily-question&envId=2024-02-04
public class Day4_P76 {
    public static void main(String[] args) {
        String s = StringUtils.generateRandomStr(25);
        String t = StringUtils.generateStringInStr(s, 5);
        System.out.println("Original Str:" + s);
        System.out.println("Want to include:" + t);
        System.out.println(minWindow(s, t));
    }


    //Given two strings s and t of lengths m and n respectively,
    //return the minimum window substring of s such that
    //every character in t (including duplicates) is included in the window.
    //If there is no such substring, return the empty string "".
    //The testcases will be generated such that the answer is unique.

    //Input: s = "ADOBECODEBANC", t = "ABC"
    //Output: "BANC"
    public static String minWindow(String s, String t) {
        char[] str = s.toCharArray();
        char[] target = t.toCharArray();
        int R = 0;
        int ans = Integer.MAX_VALUE;
        int start = -1;
        int remain = 0; //indict how many coins still need to return.
        int[] loan = new int[128];
        int[] targetMap = new int[128];
        for(int i = 0; i < target.length; i++) {
            loan[target[i] - 'A']++;
            targetMap[target[i] - 'A']++;
            remain++;
        }
        for(int L = 0; L < str.length && R < str.length;) {
            //only when --loan[str[R] - 'A'] still >= 0, remain can be reduced.
            //loan[str[R] - 'A'] < 0 means this 'coin' has been wiped off.
            while(R < str.length && remain > 0) {
                if(targetMap[str[R] - 'A'] > 0) {
                    if(--loan[str[R] - 'A'] >= 0) {
                        remain--;
                    }
                }
                R++;
             }
            while(remain == 0) {
                if(R - L < ans) {
                    ans = R - L;
                    start = L;
                }
                if(targetMap[str[L] - 'A'] > 0) {
                    //same as above, only when the ++loan[str[L] - 'A'] > 0
                    //means that this coin is in debt state.
                    if(++loan[str[L] - 'A'] > 0) {
                        remain++;
                    }
                }
                L++;
            }
        }
        return start == -1 ? "" : s.substring(start, start + ans);
    }

    public static String minWindowBrute(String s, String t) {
        char[] str = s.toCharArray();
        char[] target = t.toCharArray();
        int remain = 0; //indict how many coins still need to return.
        int[] loan = new int[128];
        int[] targetMap = new int[128];
        for(int i = 0; i < target.length; i++) {
            loan[target[i] - 'A']++;
            targetMap[target[i] - 'A']++;
            remain++;
        }
        for(int L = 0; L < str.length; L++) {
            for(int R = L; R < str.length; R++) {

            }
        }

        return "";
    }

}
